package com.leetcode.LC_MED;

import java.util.Arrays;

public class LC518 {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        int[] count = new int[amount + 1];
        Arrays.fill(count, 1);
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j] == dp[j - coins[i]] + coins[i]) {
                    count[j] += count[j - coins[i]];
                } else if (dp[j] < dp[j - coins[i]] + coins[i]) {
                    count[j] = count[j - coins[i]];
                }
                dp[j] = Math.max(dp[j], dp[j - coins[i]] + coins[i]);
            }
        }
        return dp[amount] == amount ? count[amount] : 0;
    }
}
